package main.java.com.amanda.suafa;

import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;
import main.java.com.amanda.innovate.EdgeWeightedDirectedCycle;
import main.java.com.amanda.utils.DirectedEdge;
import main.java.com.amanda.utils.EdgeWeightedDigraph;

import java.util.Scanner;

/**
 * @author amanda
 * @Description 算法4.11 基于队列的Bellman-Ford算法
 * 有负权重的最短路径
 */
public class BellmanFordSP {
    private double[] distTo;         // 从起点到某个顶点的路径长度
    private DirectedEdge[] edgeTo;  // 从起点到某个顶点的最后一条边
    private boolean[] onQ;          // 该顶点是否存在于队列
    private Queue<Integer> queue;   // 正在被放松的顶点
    private int cost;               // relax() 的调用次数
    private Iterable<DirectedEdge> cycle;// edgeTo[] 中是否有负权重环

    public BellmanFordSP(EdgeWeightedDigraph G, int s) {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        onQ = new boolean[G.V()];
        queue = new Queue<>();
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;
        queue.enqueue(s);
        onQ[s] = true;
        while (!queue.isEmpty() && !hasNegativeCycle()) {
            int v = queue.dequeue();
            onQ[v] = false;
            relax(G, v);
        }
    }

    public double distTo(int v) {
        return distTo[v];
    }

    public boolean hasPathTo(int v) {
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    public Iterable<DirectedEdge> pathTo(int v) {
        if (!hasPathTo(v))
            return null;
        Stack<DirectedEdge> path = new Stack<>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])
            path.push(e);
        return path;
    }

    private void relax(EdgeWeightedDigraph G, int v) {
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.weight()) {
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
                if (!onQ[w]) {
                    queue.enqueue(w);
                    onQ[w] = true;
                }
            }
            if (cost++ % G.V() == 0)
                findNegativeCycle();
        }
    }

    private void findNegativeCycle() {
        int V = edgeTo.length;
        EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
        for (int v = 0; v < V; v++) {
            if (edgeTo[v] != null) {
                spt.addEdge(edgeTo[v]);
            }
        }
        EdgeWeightedDirectedCycle cf = new EdgeWeightedDirectedCycle(spt);
        cycle = cf.cycle();
    }

    private boolean hasNegativeCycle() {
        return cycle != null;
    }

    public Iterable<DirectedEdge> negativeCycle() {
        return cycle;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(scanner);
        int s = scanner.nextInt();
        BellmanFordSP sp = new BellmanFordSP(G, s);

        if (sp.hasNegativeCycle()) {
            for (DirectedEdge e : sp.negativeCycle())
                StdOut.println(e);
        }

        else {
            for (int v = 0; v < G.V(); v++) {
                if (sp.hasPathTo(v)) {
                    StdOut.printf("%d to %d (%5.2f)  ", s, v, sp.distTo(v));
                    for (DirectedEdge e : sp.pathTo(v)) {
                        StdOut.print(e + "   ");
                    }
                    StdOut.println();
                }
                else {
                    StdOut.printf("%d to %d           no path\n", s, v);
                }
            }
        }
    }
}
/*
8
15
4 5  0.35
5 4  0.35
4 7  0.37
5 7  0.28
7 5  0.28
5 1  0.32
0 4  0.38
0 2  0.26
7 3  0.39
1 3  0.29
2 7  0.34
6 2 -1.20
3 6  0.52
6 0 -1.40
6 4 -1.25
0
0 to 0 ( 0.00)
0 to 1 ( 0.93)  0->2 0.26   2->7 0.34   7->3 0.39   3->6 0.52   6->4 -1.25   4->5 0.35   5->1 0.32
0 to 2 ( 0.26)  0->2 0.26
0 to 3 ( 0.99)  0->2 0.26   2->7 0.34   7->3 0.39
0 to 4 ( 0.26)  0->2 0.26   2->7 0.34   7->3 0.39   3->6 0.52   6->4 -1.25
0 to 5 ( 0.61)  0->2 0.26   2->7 0.34   7->3 0.39   3->6 0.52   6->4 -1.25   4->5 0.35
0 to 6 ( 1.51)  0->2 0.26   2->7 0.34   7->3 0.39   3->6 0.52
0 to 7 ( 0.60)  0->2 0.26   2->7 0.34
 */
